The present invention relates generally to the field of information display. More specifically, it provides methods for the construction and manipulation of displays of tree-structured information in a tabular form permitting rapid identification of “root-to-leaf” paths, and facilitating deeper exploration of those paths both within the tree representation, and also via auxiliary displays keyed to the latter.
To establish some terminology, a “tree” or “tree structure” is a standard term denoting an abstract data structure that models information as a set of nodes connected by directed edges such that: (a) there is exactly one element having no incoming edges, called the “root”; and (b) all other nodes have exactly one incoming edge. A leaf node is a node with no outgoing edges. All nodes besides the root node and the leaf nodes can be called “interior nodes”. The “parent” of a node is the source of its incoming edge, and the “children” of a node are the targets of its outgoing edges. A “path” in a tree is a sequence of nodes such that each node except the last in the sequence is followed by one of its children.
The invention is intended for use in connection with tree structures whose paths form logical groupings, and whose interior nodes represent substantial amounts of information (rather than acting as simple containers, like file directories). For example, the nodes of inheritance trees, such as natural taxonomies or programming-language frameworks, represent collections of properties, and the paths determine the net properties inherited by an interior node or leaf. As another example, the nodes of trees used to depict email threads represent individual messages, and the paths constitute the synchronous message/response sequences within the thread. For such applications, tree visualizations should provide a convenient grasp of path relationships, while at the same time containing sufficient text to serve as overviews of tree content. Furthermore, the tree visualizations should also serve as contexts for deeper exploration of information along the paths.
Conventional representations of tree-structured material do not have these properties. Tree-structured material is conventionally visualized via either connected node-edge representations, or linear, indented representations. Both of these representations tend to waste space that might be devoted to text, and to obscure path information, in different ways. Node-edge representations have significant wasted space. To limit this while providing significant labeling information, they tend to physically intersperse unrelated paths. The alternative of using tiny nodes can partially solve this latter problem, but at the expense of omitting any information about node content. In linear, indented representations, any line may contain only textual information for one node, and nodes may appear at considerable distances from their ancestors, so that individual paths are difficult to isolate.
Furthermore, while conventional tree representations sometimes provide for selection and display of the full text underlying individual nodes, they do so one-node-at-a-time. This mechanism is inadequate and onerous in cases where there are many nodes, and the relationships among connected nodes are significant.
There are two relatively recent approaches to the display of tree-structured information that address some of the disadvantages of conventional node-edge visualizations. First, the “TreeMap” visualization, described by B. Johnson and B. Shneiderman in the paper “TreeMaps: A Space-Filling Approach to the Visualization of Hierarchic Information Structures, Proceedings of 1991 IEEE Visualization Conference, focuses on avoiding waste of space for trees whose interior nodes function as organizers or containers, mapping the tree into a nested rectangular structure, with the rectangles sized proportionately to the size of the nodes they contain, or other distinguishing principle. This approach addresses the waste-of-space problem, but only for leaf nodes, and does not alleviate, and in some cases exacerbates, the path visualization problem. Another approach is the “Degree of Interest” tree visualization, as described in a U.S. patent application Ser. No. 09/747,634, titled “System and Method for Browsing Node-Link Structures Based on Estimated Degree of Interest”, by Card et al., and incorporated by reference hereinabove. The Degree of Interest tree visualization is a node+edge visualization that permits the selection of a particular node of interest, and expands that node and (proportional to distance from the selected node) closely related nodes and their associated text, at the expense of more distant nodes. Such an approach could be modified to enlarge all nodes on a path from the root to a selected node, but this would allow only one such path to be easily seen at any particular time.
The present invention addresses the path comprehension problem directly, by converting the tree-structured material into a table-like structure, hereinafter called a “treetable” in which each path is represented by a column of the table. In this way, the ancestors of a given node can be seen at a glance. Furthermore, all children of a node are placed directly under that node, and can also be seen at a glance. Wastage of space is avoided in the sense that no space is devoted to the presentation of edges, and more space is available for the display of content for what may be the more important nodes, namely, those serving as roots to the broadest subtrees.
However, as in any other tree representation, the size and shape of the tree of the tree determines how much content may be given for the nodes within a limited display area, so that for large trees the amount of information that can be given for nodes within an initial visualization may be insufficient. The present invention addresses this problem in two ways. First, it adapts some methods associated with “degree of interest” displays to allow selective expansion of focus areas in ways consistent with the table-like geometry. In particular, it adapts mechanisms of (a) U.S. patent application Ser. No. 09/747,634, titled “System and Method for Browsing Node-Link Structures Based on Estimated Degree of Interest”, by Card et al., and (b) U.S. Pat. No. 6,085,202, entitled “Method and System for Producing a Table Image Having Focus and Context Regions”, which are incorporated by reference hereinabove. The second means by which the present invention addresses the problem of displaying large trees is by providing for the extraction of treatable subparts into auxiliary displays, so that more space is available for text in those subparts, while retaining the original representation, in either full-scale or outline form, to maintain user awareness of context.
But no matter how much information may be incorporated within a table-like tree representation, the individual nodes may represent far more material than can be accommodated in a single display. Many applications of conventional tree displays, such as indented file directories or indented listings of messages within an email thread, allow the user to select individual nodes for separate display. This, however, is less than satisfactory for applications where the nodes are logically related. Therefore, the present invention provides for the use of treetables as guides for reading the concatenated content of closely related nodes representing either full paths or children of the same root. The content presented may be the full content, or may be abbreviated in ways appropriate to the application. For example, an application presenting a path of an inheritance hierarchy permitting property overrides, such as a programming language class hierarchy might highlight properties of predecessors not overridden by the leaf node.
While the method provided by the invention in the area of auxiliary displays of node content is a general one, one embodiment of the invention directed specifically to the production of auxiliary displays of messages in email threads utilizes a technique which is discussed in U.S. patent application Ser. No. 09/732,024, titled “Method and System for Presenting Email Threads as Semi-connected Text by Removing Redundant Material”, by Newman et al., incorporated by reference hereinabove. This patent describes the concatenation of the significant texts of the messages of an email thread, shorn of extraneous information such as redundant quotes and contact information, into a single document. The present invention further exploits the methods of U.S. patent application Ser. No. 09/732,024 to present the concatenated messages with even more quote information elided, because of their presence in an adjacent node.
Further advantages of the invention will become apparent as the following description proceeds.